这其实是一道树链剖分的板题,难在读题...
借一下洛谷的图:(将边看成无向的)

如果理解了题目,我们会发现:
1.安装一个软件需要将号软件到号软件的路径上所有未安装的软件安装。
2.删除一个软件需要将以为根的子树上所有安装的软件删除。
其实它们分别是路径修改和子树修改,树链剖分后线段树维护区间安装的软件个数就好了。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f
const int MAXN = 100000;
int n , q , cnt;
int Fa[ MAXN + 5 ] , Size[ MAXN + 5 ] , Depth[ MAXN + 5 ] , Heaviest_son[ MAXN + 5 ];
int Dfn[ MAXN + 5 ] , Top[ MAXN + 5 ] , Rank[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
struct Point{
int l , r , num , Lazy;
};
struct Segment_Tree{
Point Tree[ 4 * MAXN + 5 ];
void Build( int x , int l , int r ) {
Tree[ x ].l = l , Tree[ x ].r = r , Tree[ x ].Lazy = -1 , Tree[ x ].num = 0;
if( l == r )
return;
int Mid = ( l + r ) / 2;
Build( ls , l , Mid );
Build( rs , Mid + 1 , r );
}
void Pushdown( int x ) {
if( Tree[ x ].Lazy == 0 ) {
Tree[ ls ].num = Tree[ rs ].num = 0;
Tree[ ls ].Lazy = Tree[ rs ].Lazy = 0;
Tree[ x ].Lazy = -1;
}
if( Tree[ x ].Lazy == 1 ) {
Tree[ ls ].num = ( Tree[ ls ].r - Tree[ ls ].l + 1 );
Tree[ rs ].num = ( Tree[ rs ].r - Tree[ rs ].l + 1 );
Tree[ ls ].Lazy = Tree[ rs ].Lazy = 1;
Tree[ x ].Lazy = -1;
}
}
void Insert( int x , int l , int r , int k ) {
if( r < Tree[ x ].l || Tree[ x ].r < l )
return;
if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
Tree[ x ].num = k ? ( Tree[ x ].r - Tree[ x ].l + 1 ) : 0;
Tree[ x ].Lazy = k;
return;
}
Pushdown( x );
Insert( ls , l , r , k );
Insert( rs , l , r , k );
Tree[ x ].num = ( Tree[ ls ].num + Tree[ rs ].num );
}
int Find( int x , int l , int r ) {
if( r < Tree[ x ].l || Tree[ x ].r < l )
return 0;
if( l <= Tree[ x ].l && Tree[ x ].r <= r )
return Tree[ x ].num;
Pushdown( x );
return Find( ls , l , r ) + Find( rs , l , r );
}
int Query_ins( int u , int v ) {
int Ans = 0;
while( Top[ u ] != Top[ v ] ) {
if( Depth[ Top[ u ] ] < Depth[ Top[ v ] ] )
swap( u , v );
Ans += ( Depth[ u ] - Depth[ Top[ u ] ] + 1 ) - Find( 1 , Dfn[ Top[ u ] ] , Dfn[ u ] );
Insert( 1 , Dfn[ Top[ u ] ] , Dfn[ u ] , 1 );
u = Fa[ Top[ u ] ];
}
if( Depth[ u ] > Depth[ v ] )
swap( u , v );
Ans += ( Depth[ v ] - Depth[ u ] + 1 ) - Find( 1 , Dfn[ u ] , Dfn[ v ] );
Insert( 1 , Dfn[ u ] , Dfn[ v ] , 1 );
return Ans;
}
int Query_uni( int u ) {
int Ans = Find( 1 , Dfn[ u ] , Dfn[ u ] + Size[ u ] - 1 );
Insert( 1 , Dfn[ u ] , Dfn[ u ] + Size[ u ] - 1 , 0 );
return Ans;
}
}Tree;
void dfs1( int u , int fa ) {
Fa[ u ] = fa , Depth[ u ] = Depth[ fa ] + 1 , Size[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs1( v , u );
Size[ u ] += Size[ v ];
if( Size[ Heaviest_son[ u ] ] < Size[ v ] )
Heaviest_son[ u ] = v;
}
}
void dfs2( int u , int top ) {
Top[ u ] = top , Dfn[ u ] = ++ cnt , Rank[ cnt ] = u;
if( !Heaviest_son[ u ] ) return;
dfs2( Heaviest_son[ u ] , top );
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !Dfn[ v ] ) dfs2( v , v );
}
}
int u , v;
char op[ 20 ];
int main( ) {
scanf("%d",&n);
for( int i = 2 ; i <= n ; i ++ ) {
scanf("%d",&v);v ++;
Graph[ i ].push_back( v );
Graph[ v ].push_back( i );
}
dfs1( 1 , 0 );
dfs2( 1 , 1 );
Tree.Build( 1 , 1 , n );
scanf("%d",&q);
for( int i = 1 ; i <= q ; i ++ ) {
scanf("%s %d",op,&u);u ++;
if( op[ 0 ] == 'i' )
printf("%d\n", Tree.Query_ins( 1 , u ) );
if( op[ 0 ] == 'u' )
printf("%d\n", Tree.Query_uni( u ) );
}
return 0;
}